/*
 * Copyright (c) 2001-2008 Caucho Technology, Inc.  All rights reserved.
 *
 * The Apache Software License, Version 1.1
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution, if
 *    any, must include the following acknowlegement:
 *       "This product includes software developed by the
 *        Caucho Technology (http://www.caucho.com/)."
 *    Alternately, this acknowlegement may appear in the software itself,
 *    if and wherever such third-party acknowlegements normally appear.
 *
 * 4. The names "Burlap", "Resin", and "Caucho" must not be used to
 *    endorse or promote products derived from this software without prior
 *    written permission. For written permission, please contact
 *    info@caucho.com.
 *
 * 5. Products derived from this software may not be called "Resin"
 *    nor may "Resin" appear in their names without prior written
 *    permission of Caucho Technology.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL CAUCHO TECHNOLOGY OR ITS CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * @author Scott Ferguson
 */

package com.caucho.hessian.util;

/**
 * The IntMap provides a simple hashmap from keys to integers. The API is an
 * abbreviation of the HashMap collection API.
 *
 * <p>
 * The convenience of IntMap is avoiding all the silly wrapping of integers.
 */
public class IntMap {
	/**
	 * Encoding of a null entry. Since NULL is equal to Integer.MIN_VALUE, it's
	 * impossible to distinguish between the two.
	 */
	public final static int NULL = 0xdeadbeef; // Integer.MIN_VALUE + 1;

	private Object[] _keys;
	private int[] _values;

	private int _size;
	private int _prime;

	/**
	 * Create a new IntMap. Default size is 16.
	 */
	public IntMap() {
		int capacity = 1024;

		_keys = new Object[capacity];
		_values = new int[capacity];

		_prime = getBiggestPrime(_keys.length);
		_size = 0;
	}

	/**
	 * Clear the hashmap.
	 */
	public void clear() {
		final Object[] keys = _keys;
		final int[] values = _values;

		for (int i = keys.length - 1; i >= 0; i--) {
			keys[i] = null;
			values[i] = 0;
		}

		_size = 0;
	}

	/**
	 * Returns the current number of entries in the map.
	 */
	public final int size() {
		return _size;
	}

	/**
	 * Puts a new value in the property table with the appropriate flags
	 */
	public final int get(Object key) {
		int prime = _prime;
		int hash = hashCode(key) % prime;
		// int hash = key.hashCode() & mask;

		final Object[] keys = _keys;

		while (true) {
			Object mapKey = keys[hash];

			if (mapKey == null)
				return NULL;
			else if (mapKey == key)
				return _values[hash];

			hash = (hash + 1) % prime;
		}
	}

	/**
	 * Puts a new value in the property table with the appropriate flags
	 */
	public final int put(Object key, int value, boolean isReplace) {
		int prime = _prime;
		int hash = hashCode(key) % prime;
		// int hash = key.hashCode() % prime;

		Object[] keys = _keys;

		while (true) {
			Object testKey = keys[hash];

			if (testKey == null) {
				keys[hash] = key;
				_values[hash] = value;

				_size++;

				if (keys.length <= 4 * _size)
					resize(4 * keys.length);

				return NULL;
			} else if (key != testKey) {
				hash = (hash + 1) % prime;

				continue;
			} else if (isReplace) {
				int old = _values[hash];

				_values[hash] = value;

				return old;
			} else {
				return _values[hash];
			}
		}
	}

	/**
	 * Expands the property table
	 */
	private void resize(int newSize) {
		Object[] keys = _keys;
		int values[] = _values;

		_keys = new Object[newSize];
		_values = new int[newSize];
		_size = 0;

		_prime = getBiggestPrime(_keys.length);

		for (int i = keys.length - 1; i >= 0; i--) {
			Object key = keys[i];

			if (key != null) {
				put(key, values[i], true);
			}
		}
	}

	protected int hashCode(Object value) {
		return value.hashCode();
	}

	public String toString() {
		StringBuffer sbuf = new StringBuffer();

		sbuf.append("IntMap[");
		boolean isFirst = true;

		for (int i = 0; i <= _keys.length; i++) {
			if (_keys[i] != null) {
				if (!isFirst)
					sbuf.append(", ");

				isFirst = false;
				sbuf.append(_keys[i]);
				sbuf.append(":");
				sbuf.append(_values[i]);
			}
		}
		sbuf.append("]");

		return sbuf.toString();
	}

	public static final int[] PRIMES = { 1, /* 1<< 0 = 1 */
			2, /* 1<< 1 = 2 */
			3, /* 1<< 2 = 4 */
			7, /* 1<< 3 = 8 */
			13, /* 1<< 4 = 16 */
			31, /* 1<< 5 = 32 */
			61, /* 1<< 6 = 64 */
			127, /* 1<< 7 = 128 */
			251, /* 1<< 8 = 256 */
			509, /* 1<< 9 = 512 */
			1021, /* 1<<10 = 1024 */
			2039, /* 1<<11 = 2048 */
			4093, /* 1<<12 = 4096 */
			8191, /* 1<<13 = 8192 */
			16381, /* 1<<14 = 16384 */
			32749, /* 1<<15 = 32768 */
			65521, /* 1<<16 = 65536 */
			131071, /* 1<<17 = 131072 */
			262139, /* 1<<18 = 262144 */
			524287, /* 1<<19 = 524288 */
			1048573, /* 1<<20 = 1048576 */
			2097143, /* 1<<21 = 2097152 */
			4194301, /* 1<<22 = 4194304 */
			8388593, /* 1<<23 = 8388608 */
			16777213, /* 1<<24 = 16777216 */
			33554393, /* 1<<25 = 33554432 */
			67108859, /* 1<<26 = 67108864 */
			134217689, /* 1<<27 = 134217728 */
			268435399, /* 1<<28 = 268435456 */
	};

	public static int getBiggestPrime(int value) {
		for (int i = PRIMES.length - 1; i >= 0; i--) {
			if (PRIMES[i] <= value)
				return PRIMES[i];
		}

		return 2;
	}
}
